package main

import "fmt"

func main() {
	root := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}

	// root := &TreeNode{
	// 	Val: 1,
	// 	Left: &TreeNode{
	// 		Val: 2,
	// 	},
	// }
	// fmt.Println(maxDepth(root))
	// mlr(root)
	bfs(root)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth1(root *TreeNode) int {
	var stack []*TreeNode
	if root == nil {
		return 0
	}
	p := root
	for {
		stack = append(stack, p)
		if p.Left != nil {
			p = p.Left
			continue
		}
		stack = stack[:len(stack)-1]
		p = stack[len(stack)-1]
		if p.Right != nil {
			p = p.Right
			continue
		}
	}
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	stack := []struct {
		node  *TreeNode
		depth int
	}{{root, 1}}
	maxDepth := 0

	for len(stack) > 0 {
		current := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if current.depth > maxDepth {
			maxDepth = current.depth
		}

		if current.node.Right != nil {
			stack = append(stack, struct {
				node  *TreeNode
				depth int
			}{
				current.node.Right, current.depth + 1,
			})
		}
		if current.node.Left != nil {
			stack = append(stack, struct {
				node  *TreeNode
				depth int
			}{
				current.node.Left, current.depth + 1,
			})
		}
	}
	return maxDepth
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
var stack []*TreeNode
	depth := 0
	if root == nil {
		return 0
	}

	l := root
	stack = append(stack, root)
	for {
		l = l.Left
		if l != nil {
			stack = append(stack, l)
			if len(stack) > depth {
				depth = len(stack)
			}
		} else {
			l = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if l.Right != nil {
				stack = append(stack, l.Right)
				if len(stack) > depth {
					depth = len(stack)
				}
				l = l.Right
			} else {
				if len(stack) == 0 {
					return depth + 1
				}

				l = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				if l.Right != nil {
					stack = append(stack, l.Right)
					if len(stack) > depth {
						depth = len(stack)
					}
					l = l.Right

				}
			}
		}
	}
		**/

func dfs(root *TreeNode) {
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		p := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		fmt.Println(p.Val)

		if p.Right != nil {
			stack = append(stack, p.Right)
		}

		if p.Left != nil {
			stack = append(stack, p.Left)
		}
	}
}

func bfs(root *TreeNode) {
	q := []*TreeNode{root}
	for len(q) > 0 {
		s := len(q)

		for i := 0; i < s; i++ {
			n := q[0]
			fmt.Println(n.Val)
			q = q[1:]
			if n.Left != nil {
				q = append(q, n.Left)
			}

			if n.Right != nil {
				q = append(q, n.Right)
			}
		}
	}
}
